package recursion

// ------------------------------arrayMinSum-------------------------------------
/*
题目： 一个数组内，每个位置左边比当前位置小的数的总和叫这个数的小和，求数组总小和的累加值
如：[1,3,4,2,5]
1左边没数
3 => 1
4 => 3 1
2 => 1
5 => 2 4 3 1
结果 = 1 + 3 + 1 + 1 + 2 + 4 + 3 + 1 = 16
*/
func ArrayMinSum(data []int) int {
	cnt := len(data)
	if cnt < 2 {
		return 0
	}

	return mergeSort(&data, 0, cnt-1)
}

func mergeSort(data *[]int, s, e int) int {
	if s == e {
		return 0
	}

	m := s + ((e - s) >> 1)

	return mergeSort(data, s, m) + mergeSort(data, m+1, e) + merge(data, s, m, e)
}

func merge(data *[]int, s, m, e int) int {
	tmp, p1, p2, ret := []int{}, s, m+1, 0
	for p1 <= m && p2 <= e {
		if (*data)[p1] < (*data)[p2] {
			tmp = append(tmp, (*data)[p1])
			ret += (*data)[p1] * (e - p2 + 1)
			p1++
		} else {
			tmp = append(tmp, (*data)[p2])
			p2++
		}
	}
	for p1 <= m {
		tmp = append(tmp, (*data)[p1])
		p1++
	}
	for p2 <= e {
		tmp = append(tmp, (*data)[p2])
		p2++
	}

	for k, v := range tmp {
		(*data)[s+k] = v
	}
	return ret
}

// ------------------------------arrayMinSum-------------------------------------

// ------------------------------reversePairs-------------------------------------
// 求数组内逆序对 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
var tmp []int

func ReversePairs(nums []int) int {
	cnt := len(nums)
	if cnt < 2 {
		return 0
	}

	tmp = make([]int, cnt)

	return mergeSort1(&nums, 0, cnt-1)
}

func mergeSort1(data *[]int, s, e int) int {
	if s == e {
		return 0
	}
	m := s + ((e - s) >> 1)

	return mergeSort1(data, s, m) + mergeSort1(data, m+1, e) + merge1(data, s, m, e)
}

func merge1(data *[]int, s, m, e int) int {
	for i := s; i <= e; i++ {
		tmp[i] = (*data)[i]
	}

	p1, p2, ret := s, m+1, 0
	for i := s; i <= e; i++ {
		if p1 == m+1 {
			(*data)[i] = tmp[p2]
			p2++
		} else if p2 == e+1 {
			(*data)[i] = tmp[p1]
			p1++
		} else {
			if tmp[p1] <= tmp[p2] {
				(*data)[i] = tmp[p2]
				p2++
			} else {
				(*data)[i] = tmp[p1]
				ret += e - p2 + 1
				p1++
			}
		}
	}

	return ret
}

// ------------------------------reversePairs-------------------------------------
